#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hashMap;
        for (auto e : nums) {
            hashMap[e]++;
        }
        vector<pair<int, int>> v(hashMap.begin(), hashMap.end());
        sort(v.begin(), v.end(), [&](pair<int, int>& p1, pair<int, int>& p2) {
            return p1.second > p2.second;
            });
        vector<int> ret;
        for (int i = 0; i < k; i++) {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

class Solution {
    struct cmp {
        bool operator()(pair<int, int>& p1, pair<int, int>& p2) {
            return p1.second < p2.second;
        }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hashMap;
        for (auto e : nums) {
            hashMap[e]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> heap(hashMap.begin(), hashMap.end());
        vector<int> ret;
        while (k--) {
            ret.push_back(heap.top().first);
            heap.pop();
        }
        return ret;
    }
};

class Solution {
    struct cmp {
        bool operator()(pair<int, int>& p1, pair<int, int>& p2) {
            return p1.second > p2.second;
        }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hashMap;
        for (auto e : nums) {
            hashMap[e]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> heap;
        for (auto& [a, b] : hashMap) {
            if (heap.size() != k) {
                heap.push({ a, b });
            }
            else {
                if (heap.top().second < b) {
                    heap.pop();
                    heap.push({ a, b });
                }
            }
        }
        vector<int> ret;
        while (!heap.empty()) {
            ret.push_back(heap.top().first);
            heap.pop();
        }
        return ret;
    }
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
 
class Solution {
    vector<int> v;

public:
    void InOrder(TreeNode* root) {
        if (root == nullptr) return;
        InOrder(root->left);
        v.push_back(root->val);
        InOrder(root->right);
    }

    TreeNode* _balanceBST(vector<int>& v, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(v[mid]);
        root->left = _balanceBST(v, left, mid - 1);
        root->right = _balanceBST(v, mid + 1, right);
        return root;
    }

    TreeNode* balanceBST(TreeNode* root) {
        InOrder(root);
        return _balanceBST(v, 0, v.size() - 1);
    }
};